using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;

namespace Mindless
{
    /// <summary>
    /// A pile of cards. It is possible to enumerate the cards, remove cards, re-add cards,
    /// etc., but not add new cards to the pile.
    /// </summary>
    /// <remarks>
    /// A pile consists of an array of cards for each suit, sorted by rank. When a card is
    /// removed from the pile, its slot is nulled out. A map of each card's index within
    /// its array is maintained in order to facilitate easy removal of cards. 
    /// </remarks>
    public class Pile : IEnumerable<Card>
    {
        /// <summary>
        /// Creates a pile that holds the given cards.
        /// </summary>
        public Pile(IEnumerable<Card> cards)
        {
                // calculate the total number of cards, and of each suit
            int total = 0;
            this.suitCount = new int[Settings.SuitCount];
            foreach (Card card in cards)
            {
                total += 1;
                this.suitCount[(int) card.Suit] += 1;
            }
                // allocate arrays to hold the cards
            this.cards = new Card[Settings.SuitCount][];
            for (int suit = 0; suit < Settings.SuitCount; ++suit)
            {
                int nCards = this.suitCount[suit];
                this.cards[suit] = new Card[nCards];
            }
                // place the cards into the arrays
            int[] suitIndex = new int[Settings.SuitCount];
            foreach (Card card in cards)
            {
                Card[] subarray = this.cards[(int) card.Suit];
                int index = suitIndex[(int) card.Suit]++;
                subarray[index] = card;
            }
                // sort the arrays and build the lookup index
            this.lookup = new FastDictionary<Card, int>(Settings.RankCount * Settings.SuitCount, -1);
            for (int suit = 0; suit < Settings.SuitCount; ++suit)
            {
                Card[] subarray = this.cards[suit];
                Array.Sort<Card>(subarray);

                for (int index = 0; index < subarray.Length; ++index)
                    this.lookup[subarray[index]] = index;
            }

            Debug.Assert(this.Count == total);
        }

        /// <summary>
        /// Creates a copy of the given pile.
        /// </summary>
        public Pile(Pile pile) : this((IEnumerable<Card>) pile)
        {
        }

        /// <summary>
        /// Cards in the pile.
        /// </summary>
        protected Card[/*suit*/][/*rank*/] cards;

        /// <summary>
        /// Count of the number of cards of each suit. This may differ from the size of the corresponding sub-array
        /// within the master jagged array (due to cards being removed from the pile).
        /// </summary>
        protected int[] suitCount;

        /// <summary>
        /// Reverse lookup index for quick addition/removal of cards.
        /// </summary>
        protected IDictionary<Card, int /*index of card*/> lookup;

        /// <summary>
        /// Answers a collection of the pile's cards in random order. This does not alter the receiver.
        /// </summary>
        public List<Card> Shuffle()
        {
                // get the receiver's cards in order
            List<Card> cards = new List<Card>(this);

                // shuffle them
            for (int iCard = 0; iCard < this.Count; ++iCard)
            {
                int iSwap = Settings.NextRandom(this.Count);
                Card c = cards[iCard];
                cards[iCard] = cards[iSwap];
                cards[iSwap] = c;
            }

            return cards;
        }

        /// <summary>
        /// Enumerates the cards in this pile (sorted by suit, then rank).
        /// </summary>
        IEnumerator<Card> IEnumerable<Card>.GetEnumerator()
        {
            for (int suit = 0; suit < Settings.SuitCount; ++suit)
            {
                Card[] suitCards = this.cards[suit];
                for (int iCard = 0; iCard < suitCards.Length; ++iCard)
                {
                    Card card = suitCards[iCard];
                    if (card != null)
                        yield return card;
                }
            }
        }

        /// <summary>
        /// Enumerates the cards in this pile (sorted by suit, then rank).
        /// </summary>
        public IEnumerator GetEnumerator()
        {
            return ((IEnumerable<Card>) this).GetEnumerator();
        }

        /// <summary>
        /// Resulting string is sorted by suit first, then descending by rank.
        /// </summary>
        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();

            bool isFirstSuit = true;
            for (int iSuit = 0; iSuit < this.cards.Length; ++iSuit)
            {
                bool isFirstCard = true;
                Card[] cards = this.cards[iSuit];
                for (int iCard = cards.Length - 1; iCard >= 0; --iCard)
                {
                    Card card = cards[iCard];
                    if (card != null)
                    {
                        if (isFirstCard && !isFirstSuit)
                            sb.Append(" ");
                        sb.Append(Card.RankChar(card.Rank));
                        isFirstSuit = isFirstCard = false;
                    }
                }
                if (!isFirstCard)
                    sb.Append(Card.SuitChar((Card.SuitEnum) iSuit));
            }

            return sb.ToString();
        }

        /// <summary>
        /// Answers a list of cards identified by the given string. E.g. "KQC 8D JH 82S".
        /// </summary>
        protected static IList<Card> ParseRaw(string s)
        {
            IList<Card> cards = new List<Card>();
            foreach (string chunk in s.Split(' '))
            {
                char suitChar = chunk[chunk.Length - 1];
                Card.SuitEnum suit = Card.GetSuit(suitChar);

                for (int i = 0; i < chunk.Length - 1; ++i)
                {
                    char rankChar = chunk[i];
                    Card.RankEnum rank = Card.GetRank(rankChar);

                    Card card = Card.GetCard(rank, suit);
                    cards.Add(card);
                }
            }

            return cards;
        }

        /// <summary>
        /// Creates a new pile from the cards identified by the given string.
        /// </summary>
        public static Pile Parse(string s)
        {
            return new Pile(Parse(s));
        }

        /// <summary>
        /// Removes the given card from the pile (we assume the pile contains the card).
        /// </summary>
        /// <returns>Cookie to be used when the card is re-added to the pile.</returns>
        public int Remove(Card card)
        {
            int suit = (int) card.Suit;
            Debug.Assert(this.suitCount[suit] > 0);

            Debug.Assert(this.lookup.ContainsKey(card));
            int index = (int) this.lookup[card];
            Debug.Assert(this.cards[suit][index] == card);
            this.cards[suit][index] = null;
            this.lookup.Remove(card);
            this.suitCount[suit] -= 1;

            return index;
        }

        /// <summary>
        /// Re-adds the given card to the pile (using the given cookie, which was obtained
        /// when the card was first removed from the pile).
        /// </summary>
        public void ReAdd(Card card, int cookie)
        {
            int suit = (int) card.Suit;
            Debug.Assert(this.cards[suit][cookie] == null);
            Debug.Assert(!this.lookup.ContainsKey(card));

            this.cards[suit][cookie] = card;
            this.lookup.Add(card, cookie);
            this.suitCount[suit] += 1;
        }

        /// <summary>
        /// The number of cards in this pile.
        /// </summary>
        public int Count
        {
            get { return this.lookup.Count; }
        }

        /// <summary>
        /// Answers the number of cards of the given suit in the pile.
        /// </summary>
        public int SuitCount(Card.SuitEnum suit)
        {
            return this.suitCount[(int) suit];
        }

        /// <summary>
        /// Indicates whether this pile contains the given card.
        /// </summary>
        public bool Contains(Card card)
        {
            return this.lookup.ContainsKey(card);
        }

        /// <summary>
        /// Indicates whether this pile contains any cards of the given suit.
        /// </summary>
        public bool Contains(Card.SuitEnum suit)
        {
            Debug.Assert(this.suitCount[(int) suit] >= 0);

            return this.suitCount[(int) suit] != 0;
        }
    }

    /// <summary>
    /// Very fast but stupid dictionary. Only applicable when keys hash to a value less than the given size
    /// without collision.
    /// </summary>
    class FastDictionary<Key, Value> : IDictionary<Key, Value>
        where Value : IEquatable<Value>
    {
        /// <summary>
        /// Creates a dictionary capable of containing the given number of entries, using the given value
        /// for empty entries. Note that keys must hash to a value between 0 and size-1 without collision.
        /// </summary>
        public FastDictionary(int size, Value nullValue)
        {
            this.values = new Value[size];
            this.nullValue = nullValue;
            this.Clear();
        }

        /// <summary>
        /// Creates a dictionary capable of containing the given number of entries. Note that keys must
        /// hash to a value between 0 and size-1 without collision.
        /// </summary>
        public FastDictionary(int size) : this(size, default(Value))
        {
        }

        /// <summary>
        /// The dictionary is stored as an array of values, indexed by each key's hash.
        /// </summary>
        protected Value[] values;

        /// <summary>
        /// What to store in an empty array element. This is the only way we know it's empty.
        /// </summary>
        protected Value nullValue;

        /// <summary>
        /// Stores the given value in the given key's element.
        /// </summary>
        public void Add(Key key, Value value)
        {
            this.values[key.GetHashCode()] = value;
        }

        /// <summary>
        /// Answers false iff the given key's element contains the null value.
        /// </summary>
        public bool ContainsKey(Key key)
        {
            return !this.values[key.GetHashCode()].Equals(this.nullValue);
        }

        /// <summary>
        /// No way to know what the keys are because we don't store them.
        /// </summary>
        public ICollection<Key> Keys
        {
            get { throw new NotImplementedException(); }
        }

        /// <summary>
        /// Empties the given key's element.
        /// </summary>
        public bool Remove(Key key)
        {
            this.values[key.GetHashCode()] = this.nullValue;

            return true;
        }

        /// <summary>
        /// Answers the value stored in the given key's element.
        /// </summary>
        public bool TryGetValue(Key key, out Value value)
        {
            value = this.values[key.GetHashCode()];

            return !value.Equals(this.nullValue);
        }

        /// <summary>
        /// All non-null values in the reciever.
        /// </summary>
        public ICollection<Value> Values
        {
            get
            {
                IList<Value> values = new List<Value>();
                for (int i = 0; i < this.values.Length; ++i)
                {
                    if (!this.values[i].Equals(this.nullValue))
                        values.Add(this.values[i]);
                }

                return values;
            }
        }

        /// <summary>
        /// The value stored in the given key's element.
        /// </summary>
        public Value this[Key key]
        {
            get { return this.values[key.GetHashCode()]; }
            set { this.values[key.GetHashCode()] = value; }
        }

        /// <summary>
        /// Sets the given key's element to the given value.
        /// </summary>
        public void Add(KeyValuePair<Key, Value> item)
        {
            this.values[item.Key.GetHashCode()] = item.Value;
        }

        /// <summary>
        /// Sets all elements to the null value.
        /// </summary>
        public void Clear()
        {
            for (int i = 0; i < this.values.Length; ++i)
                this.values[i] = this.nullValue;
        }

        /// <summary>
        /// Indicates whether the value stored in the given key's element matches the given value.
        /// </summary>
        public bool Contains(KeyValuePair<Key, Value> item)
        {
            return this.values[item.Key.GetHashCode()].Equals(item.Value);
        }

        /// <summary>
        /// No way to know what the keys are because we don't store them.
        /// </summary>
        public void CopyTo(KeyValuePair<Key, Value>[] array, int arrayIndex)
        {
            throw new NotImplementedException();
        }

        /// <summary>
        /// Answers the number of non-null values in the receiver.
        /// </summary>
        public int Count
        {
            get { return this.Values.Count; }
        }

        /// <summary>
        /// Indicates whether the receiver is read-only.
        /// </summary>
        public bool IsReadOnly
        {
            get { return false; }
        }

        /// <summary>
        /// Clears the given key's element.
        /// </summary>
        public bool Remove(KeyValuePair<Key, Value> item)
        {
            return this.Remove(item.Key);
        }

        /// <summary>
        /// No way to know what the keys are because we don't store them.
        /// </summary>
        public IEnumerator<KeyValuePair<Key, Value>> GetEnumerator()
        {
            throw new NotImplementedException();
        }

        /// <summary>
        /// No way to know what the keys are because we don't store them.
        /// </summary>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }
    }
}